/* 
    给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N);
*/
let watershed = function (arr, num) {
    let point = 0;
    for (let index = 0; index < arr.length; index++) {
        const element = arr[index];
        if (element <= num) {
            arr = swap(arr, point++, index);
        }
    }
    return { arr, point };
};

function swap(array, a, b) {
    let temp = array[a];
    array[a] = array[b];
    array[b] = temp;
    return array;
}

let arr = [12, 45, 45, 78, 721, 45, 12, 4544, 54, 45, 45, 445, 454, 5, 1212, 45, 10, 1, 1];
let division = 1;
let res = watershed(arr, division);
console.log(res);
